package com.asia.algorithmcode.binaryTree;

import java.util.ArrayList;
import java.util.List;

/**
 * @DESCRIPTION: 95、不同的二叉搜索树2
 * @USER: wanfu
 * @DATE: 2025/4/24 星期四 11:13
 */
public class GenerateTrees2 {

    public static void main(String[] args) {
        List<TreeNode> treeNodes = new GenerateTrees2().generateTrees(3);

        System.out.println(treeNodes);
    }


    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new ArrayList<>();
        }
        return dfs(1, n);
    }

    private List<TreeNode> dfs(int l, int r) {
        List<TreeNode> resList = new ArrayList<>();
        if (l > r) {
            resList.add(null);
            return resList;
        }

        for (int i = l; i <= r; i++) {

            List<TreeNode> lefts = dfs(l, i - 1);
            List<TreeNode> rights = dfs(i + 1, r);

                for (TreeNode left : lefts) {
                    for (TreeNode right : rights) {
                        TreeNode root = new TreeNode(i);
                        root.left = left;
                        root.right = right;
                        resList.add(root);

                    }
                }
        }
        return resList;
    }


}
